With the advancement of computer technologies and understanding of basic physical phenomena or systems (e.g., engine operation, fluid flow, heat transfer, structural stress and strain analysis, etc.), three-dimensional (3D) computer simulation has become more of an important feature in physical system development, analysis, and evaluation. The computer simulation (modeling) often involves the building of a finite element mesh (collection of discrete set of points defined as nodes) to model the physical system. The accuracy of finite element mesh generation is related to the geometric complexity (including representing the physical system by a set of mathematical equations) of the physical system including the number of finite elements in the mesh, the order of those elements, and the quality of those finite elements.
A number of mesh-generating algorithms (e.g., parametric mapping, Dicer algorithm, Paving algorithm, Whisker-Weaving algorithm, sweeping algorithm, etc.) have been developed to attempt to generate high-quality meshes (including volume meshes) with greater accuracy and reduced user interaction for generating the mesh. However, each algorithm has its own set of strengths and weaknesses, and therefore may only be suitable for a particular geometry while being ineffective for another. Therefore, there is still a need to generate high-quality meshes for all types of geometry, including hexahedral volume meshes, that are robust, accurate, and reduce user interaction time. Additionally, modification of a volume (3D) mesh is an important feature to improving mesh quality by allowing removal of poor quality elements (e.g., inverted elements) from the mesh to generate a coarser volume mesh and more accurate analysis results.
As described herein, the generation of a dual (for a volume mesh) within a dual space may be an effective tool for producing a high-quality volume mesh for three-dimensional elements (objects) by providing an alternative geometric representation of the volume mesh and more clearly defining global connectivity constraints for the mesh. Advantageously, the dual of a mesh may be generated, edited, and then converted back to a volume mesh to improve analysis results. It is noted that terms used within the specification, in accordance with embodiments of the present invention, will be defined within the specification and further definition may be found within the Glossary of Terms in Appendix A. FIGS. 1A, 1B illustrate the process for generating a dual of a 3D element as found in the prior art. FIG. 1A shows a stack (column) 100 of 3D elements (mesh) in primal space (e.g., hexahedral elements). Each hexahedral element of the stack 100 includes six quadrilateral faces 108 and eight nodes 110 formed from three edges 112. It is noted that stack 100 may form the complete volume mesh. A dual 115 of the volume elements (mesh) 100 may be generated by connecting opposing faces of a hexahedral element using a (volume) chord 102 (see Appendix A for glossary of terms) as shown in FIG. 1B. As shown in FIG. 1B, chord 102 (a volume dual chord) connects the opposite edges for a stack of hexahedral elements 114, 116, 118, 120. In the dual space generated, chord 102 is equivalent (the dual) to the row of hexahedral elements 114, 116, 118, 120 in the primal space.
The generation of the dual may continue as shown in FIG. 1B as more opposite faces of the hexahedral elements 114, 116, 118, 120 are connected using further chords (e.g., 101, 103, 105, 107, 109). The chords are generated with adherence to the following rules: 1) a chord that begins on a boundary must terminate on the boundary, or 2) a chord may form an internal closed loop.
To help complete the dual 115, a twist plane 202 may be generated as shown in FIG. 2A (from the prior art) that carries a chord 102 along an intersecting edge. The twist plane 202 may be a continuous, three-dimensional surface which adheres to the following rule: twist planes may be nowhere tangent or coplanar. FIG. 2A found in the prior art shows three intersecting twist planes 202, 204, 206 that define a 3D cell region (hexahedral element) 208. Three-dimensional (3D) cell region 208 may be defined as an n-sided polyhedron with the faces formed by individual twist planes 202, 204, 206 that carry (formed from) chords 102, 101, 109, respectively (see glossary in Appendix A). As shown in FIG. 2B from the prior art, a centroid 216 may be formed from the three intersecting chords 101, 102, 109 generated from the intersecting twist planes 202, 204, 206 where the intersecting chords include one 3D cell region (hexahedral element) 208. FIG. 3 found in the prior art shows a twist plane 302 in a hexahedral mesh 300 that may be used to generate a sheet of hexahedral mesh elements for extraction to modify the mesh 300. As shown in FIG. 2B, every 3D cell region 208 includes a single node (e.g., node 210) from the original stack 100. Cell region 208 is equivalent (the dual) to node 210 within the dual space generated. Also, centroid 216 is equivalent (the dual) to hexahedral element 114 within the dual space generated. Also, Table 1 in Appendix B shows the relationship between the original surface elements and dual entities in three dimensions.
Therefore, due to the disadvantages of current volume meshing algorithms, there is a need to provide a computer modeling technique that uses duals to modify hexahedral volume meshes while maintaining accuracy, reduced user interaction time, and high quality of the resulting meshes to generate a coarser hexahedral volume mesh.